import java.util.*;
import java.lang.Math.*;

public class mergesort {

	public static final int INF = 1000000000;

	public void merge (int a[], int p, int q, int r) {
		int n1 = q - p + 1;
		int n2 = r - q;
		int lt[] = new int [n1 + 1];
		int rt[] = new int [n2 + 1];
		int i;
		int j;
		int k;
		
		for (i = 0; i < n1; i++) {
			lt[i] = a[p + i];
		}
		for (j = 0; j < n2; j++) {
			rt[j] = a[q + j + 1];
		}
		lt[n1] = INF;
		rt[n2] = INF;
		System.out.println (Arrays.toString (lt));
		System.out.println (Arrays.toString (rt));
		i = 0;
		j = 0;
		for (k = p; k <= r; k++) {
			System.out.print ("lt["+i+"]="+lt[i]+" rt["+j+"]="+rt[j]+" ");
			if (lt[i] <= rt[j]) {
				a[k] = lt[i];
				i++;
			} else {
				a[k] = rt[j];
				j++;
			}
			System.out.println ("i="+i+" j="+j);
		}
	}
	
	public void sort (int a[], int p, int r) {
		int q = 0;
		if (p < r) {
			q = (int) Math.floor ((p + r) / 2);
			sort (a, p, q);
			sort (a, q + 1, r);
			merge (a, p, q, r);
		}
	}
	
	public static void main (String params[]) {
		int a[] = new int[]{6,5,7,4,8,3,9,2,0,1};
		mergesort ms = new mergesort();
		
		System.out.println (Arrays.toString (a));
		ms.sort (a, 0, 9);
		//ms.merge (a, 0, 4, 9);
		System.out.println (Arrays.toString (a));
	}

}
